package leetcode.sort;

import java.util.Arrays;

/**
 * @author :songyaozhang
 * @date :Created 2021/7/14 18:07
 * @description :
 */
public class MergeSort {
    public static void main(String[] args) {
        int[] arr = {8,4,5,7,1,3,6,2};
        int[] temp = new int[arr.length];
        mergeSort(arr,0,arr.length - 1,temp);
        System.out.println(Arrays.toString(arr));
    }

    public static void mergeSort(int[] arr, int left, int right, int[]temp) {
        if (left < right) {
            int mid = left + right >> 1;
            mergeSort(arr, left, mid, temp);
            mergeSort(arr, mid + 1, right, temp);
            merge(arr, left, mid, right, temp);
        }
    }

    private static void merge(int[] arr, int left, int mid, int right, int[] temp) {
        int i = left;
        int j = mid + 1;
        int t = 0;

        while (i <= mid || j <= right) {
            temp[t++] = (i <= mid ? arr[i] : Integer.MAX_VALUE) > (j <= right ? arr[j] : Integer.MAX_VALUE) ? arr[j++] : arr[i++];
        }

        t = 0;
        int tempLeft = left;
        while (tempLeft <= right) {
            arr[tempLeft++] = temp[t++];
        }
    }
}
